﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SimpleTest
{
    class Program 
    {
        static void Main(string[] args)
        {
            //IList<IList<int>> d = Combine(5, 2);
            //int f = LengthOfLongestSubstring("dvdf");
            //int[] candidates = { 2, 3, 5 };
            //IList<IList<int>> ff = CombinationSum(candidates, 8);



            string g = LongestPalindrome("zudfweormatjycujjirzjpyrmaxurectxrtqedmmgergwdvjmjtstdhcihacqnothgttgqfywcpgnuvwglvfiuxteopoyizgehkwuvvkqxbnufkcbodlhdmbqyghkojrgokpwdhtdrwmvdegwycecrgjvuexlguayzcammupgeskrvpthrmwqaqsdcgycdupykppiyhwzwcplivjnnvwhqkkxildtyjltklcokcrgqnnwzzeuqioyahqpuskkpbxhvzvqyhlegmoviogzwuiqahiouhnecjwysmtarjjdjqdrkljawzasriouuiqkcwwqsxifbndjmyprdozhwaoibpqrthpcjphgsfbeqrqqoqiqqdicvybzxhklehzzapbvcyleljawowluqgxxwlrymzojshlwkmzwpixgfjljkmwdtjeabgyrpbqyyykmoaqdambpkyyvukalbrzoyoufjqeftniddsfqnilxlplselqatdgjziphvrbokofvuerpsvqmzakbyzxtxvyanvjpfyvyiivqusfrsufjanmfibgrkwtiuoykiavpbqeyfsuteuxxjiyxvlvgmehycdvxdorpepmsidsfgpisjerpogjeaorjtpojerpjtfdjapoerpjterpjteapofjspodjgsdmgskfsmvae[r,fas'';k[zkfoakwp[fdkf[aprak[ewf[pepojoietuioejrpowekfwereweryweywerdskfp[af[pakfsd,sd,fasdfkeroktpoerkwtpowejypijtryjerpytojertpouerkt[yweptwektrpwktrktrkreptkttttttttttttttttttttttttttttttttttttttttttqeptrpo3q4[p34pppppppppppppppppppppppppppppppppp44444444444444444444f'sldf[plldsfmsdalfmapsopnvmyzeqeiikajopqedyopirmhymozernxzaueljjrhcsofwyddkpnvcvzixdjknikyhzmstvbducjcoyoeoaqruuewclzqqqxzpgykrkygxnmlsrjudoaejxkipkgmcoqtxhelvsizgdwdyjwuumazxfstoaxeqqxoqezakdqjwpkrbldpcbbxexquqrznavcrprnydufsidakvrpuzgfisdxreldbqfizngtrilnbqboxwmwienlkmmiuifrvytukcqcpeqdwwucymgvyrektsnfijdcdoawbcwkkjkqwzffnuqituihjaklvthulmcjrhqcyzvekzqlxgddjoir");

        }


        /// <summary>
        /// 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合
        /// </summary>
        /// <param name="n">给定的整数</param>
        /// <param name="k">可能的组合种类</param>
        /// <returns>组合种类的数组</returns>
        //输入: n = 4, k = 2
        //输出:
        //[
        //  [2,4],
        //  [3,4],
        //  [2,3],
        //  [1,2],
        //  [1,3],
        //  [1,4],
        //]
        public static IList<IList<int>> Combine(int n, int k)
        {
            if (k > n || k < 0) return null;
            int[] arr = Enumerable.Range(1, n).ToArray();
            IList<IList<int>> list = new List<IList<int>>();
            foreach (int s in arr)
            {
                List<IList<int>> lst = list.Where(p => p.Count < k).ToList();
                List<int> nArr = new List<int> { s };
                list.Add(nArr);
                foreach (List<int> ss in lst) list.Add(ss.Concat(nArr).ToList());
            }
            return list.Where(o => o.Count == k).OrderByDescending(p => p.Count).ToList();
        }


        /// <summary>
        /// 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度
        /// </summary>
        /// <param name="s">输入的字符串</param>
        /// <returns>长度</returns>
        /// 
        //输入: "abcabcbb"
        //输出: 3 
        //解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
        //示例 2:

        //输入: "bbbbb"
        //输出: 1
        //解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
        //示例 3:

        //输入: "pwwkew"
        //输出: 3
        //解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
        //     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

        public static int LengthOfLongestSubstring(string s)
        {
            int n = s.Length;
            HashSet<char> set = new HashSet<char>();        //集合
            int ans = 0, start = 0, stop = 0;               //ans为字符串长度，starp区间起点，stop区间终点
            while (start < n && stop < n)
            {
                // try to extend the range [i, j]
                if (!set.Contains(s[stop]))
                {
                    set.Add(s[stop++]);
                    ans = Math.Max(ans, stop - start);
                    //或者ans = ans > (stop - start) ? ans : (stop - start)
                }
                else
                {
                    set.Remove(s[start++]);
                }
            }
            return ans;
        }


        public static string LongestPalindrome(string s)
        {
            if (s.Length == 1 || s == "") return s;
            List<string> list = new List<string>();
            for (int i = 0; i < s.Length; i++)
            {
                List<string> ele = new List<string>();
                for (int j = i + 1; j < s.Length; j++)
                {
                    string tem = s[i].ToString() + s[j].ToString();
                    if (ele.Count > 0) tem = ele[ele.Count - 1] + s[j].ToString();
                    ele.Add(tem);
                }
                for (int k = 0; k < ele.Count; k++)
                {
                    int length = 0;
                    for (int m = 0; m < ele[k].Length; m++)
                    {
                        if (ele[k][m] != ele[k][ele[k].Length - 1 - m]) break;
                        else length++;
                    }
                    if (length == ele[k].Length) list.Add(ele[k]);
                }
            }
            if (list.Count <= 0) return s[0].ToString();
            return list.OrderByDescending(o => o.Length).ToList()[0];
        }


        #region 
        static List<IList<int>> res = new List<IList<int>>();
        static List<int> temp = new List<int>();

        /// <summary>
        /// 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
        ///candidates 中的数字可以无限制重复被选取。
        /// </summary>
        /// <param name="candidates"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        /// 

        //输入：candidates = [2,3,6,7], target = 7,
        //所求解集为：
        //[
        //  [7],
        //  [2,2,3]
        //]
        //示例 2：

        //输入：candidates = [2,3,5], target = 8,
        //所求解集为：
        //[

        // [2,2,2,2],
        //  [2,3,3],
        //  [3,5]
        //]
        public static IList<IList<int>> CombinationSum(int[] candidates, int target)
        {
            SumCal(candidates, 0, 0, target);
            return res;
        }

        static void SumCal(int[] list, int sum, int start, int target)
        {
            if (sum > target) return;
            if (sum == target)
            {
                List<int> num = new List<int>(temp);
                res.Add(num);
                return;
            }
            for (int i = start; i < list.Length; i++)
            {
                sum += list[i];
                temp.Add(list[i]);
                SumCal(list, sum, i, target);
                sum -= list[i];
                temp.RemoveAt(temp.Count - 1);
            }
        }
        #endregion
    }
}
